package main

import "fmt"

func main() {
	nums := []int{1, 2, 3, 56, 77}
	fmt.Println(search(nums, 77))
}

//给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，
//写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
func search(nums []int, target int) int {
	len := len(nums)
	if len <= 0 {
		return -1
	}
	if len == 1 {
		if nums[0] == target {
			return 0
		}
		return -1
	}
	return doFind(nums, 0, len-1, target)

}

// 递归实现
func doFind(nums []int, left, right int, target int) int {
	if right < left {
		return -1
	}
	mid := (right + left) / 2
	res := nums[mid] - target
	if res == 0 {
		return mid
	} else if res < 0 {
		return doFind(nums, mid+1, right, target)
	}
	return doFind(nums, left, mid-1, target)
}

// 迭代实现
func searchIteration(nums []int, target int) int {
	len := len(nums)
	if len <= 0 {
		return -1
	}
	if len == 1 {
		if nums[0] == target {
			return 0
		}
		return -1
	}
	left := 0
	right := len - 1
	for right >= left {

		mid := (right + left) / 2

		if nums[mid] > target {
			right--
		} else if nums[mid] < target {
			left++
		} else if nums[mid] == target {
			return mid
		}
	}
	return -1

}
